	package shortestPath;

public class Dijkstra{
	public static long ShortestPathTo(int[][] matrix, boolean showAnswer) {
		long startTime = System.currentTimeMillis();

		//Create the distance array. 		
		int[][] distanceArray = new int[matrix.length][matrix.length];
		
		//Initialise the distance array.
		for(int i=0; i<matrix.length; i++){
			for(int j=0; j<matrix.length; j++){
				distanceArray[i][j] = Integer.MAX_VALUE/3;
			}
		}
		distanceArray[0][0] = matrix[0][0];
		
		//Create the boolean array. 		
		boolean[][] visitedArray = new boolean[matrix.length][matrix.length];
		
		//Initialise the boolean array.
		for(int i=0; i<matrix.length; i++){
			for(int j=0; j<matrix.length; j++){
				visitedArray[i][j] = false;
			}
		}		
		
		//
		for(int k=0; k<matrix.length*matrix.length; k++){
			int smallestDistance = Integer.MAX_VALUE, smallestI=0, smallestJ=0;
			for(int i=0; i<matrix.length; i++){
				for(int j=0; j<matrix.length; j++){

					if(smallestDistance > distanceArray[i][j] && !visitedArray[i][j]){
						smallestDistance = distanceArray[i][j];
						smallestI = i;
						smallestJ = j;
					}
				}
			}
			//&& conditions check to see if [i][j] is at the edge of the matrix.
			if(smallestI!=0 && distanceArray[smallestI][smallestJ] + matrix[smallestI-1][smallestJ] < distanceArray[smallestI-1][smallestJ]){
				distanceArray[smallestI-1][smallestJ] = distanceArray[smallestI][smallestJ] + matrix[smallestI-1][smallestJ];
			}
			if(smallestI!=matrix.length-1 && distanceArray[smallestI][smallestJ] + matrix[smallestI+1][smallestJ] < distanceArray[smallestI+1][smallestJ]){
				distanceArray[smallestI+1][smallestJ] = distanceArray[smallestI][smallestJ] + matrix[smallestI+1][smallestJ];
			}
			if(smallestJ!=0 && distanceArray[smallestI][smallestJ] + matrix[smallestI][smallestJ-1] < distanceArray[smallestI][smallestJ-1]){
				distanceArray[smallestI][smallestJ-1] = distanceArray[smallestI][smallestJ] + matrix[smallestI][smallestJ-1];
			}
			if(smallestJ!=matrix.length-1 && distanceArray[smallestI][smallestJ] + matrix[smallestI][smallestJ+1] < distanceArray[smallestI][smallestJ+1]){
				distanceArray[smallestI][smallestJ+1] = distanceArray[smallestI][smallestJ] + matrix[smallestI][smallestJ+1];
			}
			visitedArray[smallestI][smallestJ] = true;
		}

		if(showAnswer) System.out.println(distanceArray[matrix.length-1][matrix.length-1]);
		return (System.currentTimeMillis()-startTime);
	}
}
